package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/description/
 * 交换链表中的节点
 * 解题思路：
 * 1、利用快慢指针，先让 fast 走k步，然后快慢指针一起走
 * 2、这样当 fast 走到结尾时，slow指针刚好走到倒数第k个位置
 */
public class Code29_swapNodes {
    public static void main(String[] args) {
        ListNode listNode = ListNodeUtils.getLinked(1, 2, 3, 4, 5);
        int k = 2;
        ListNode res = swapNodes(listNode, k);
        ListNodeUtils.print(res);
    }

    /**
     * 快慢指针
     */
    public static ListNode swapNodes(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (--k != 0) {
            fast = fast.next;
        }
        ListNode s = fast;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        swap(s, slow);
        return head;
    }

    /**
     * 采用计数法找到倒数节点
     */
    public static ListNode swapNodes2(ListNode head, int k) {
        int n = k;
        ListNode cur = head, s = null, t;
        while (cur != null) {
            if (--n == 0) {
                s = cur;
            }
            cur = cur.next;
        }
        cur = head;
        while (n != 0) {
            cur = cur.next;
            n++;
        }
        t = cur;
        swap(s, t);
        return head;
    }

    public static void swap(ListNode x, ListNode y) {
        int t = x.val;
        x.val = y.val;
        y.val = t;
    }
}
